package 面试题;

public class MinimumEditDistance {

    public static void main(String[] args) {
        MinimumEditDistance med = new MinimumEditDistance();
        String source = "奥迪 奥迪A4L 2019款 35 TFSI 进取版 国V";
        String target = "奥迪 奥迪A4L 2019款 奥迪A4L 35 TFSI 进取型 国V";
        int result = med.similarDegree(source, target);
        //        System.out.println(result);
    }

    public int similarDegree(String source, String target) {
        if (source == null || target == null)
            throw new IllegalArgumentException("illegal input String");

        int sourceLen = source.length();
        int targetLen = target.length();

        int[][] dp = new int[sourceLen + 1][targetLen + 1];
        // init
        dp[0][0] = 0;
        for (int i = 1; i <= sourceLen; i++) dp[i][0] = i;
        for (int i = 1; i <= targetLen; i++) dp[0][i] = i;

        for (int i = 1; i <= sourceLen; i++) {
            for (int j = 1; j <= targetLen; j++) {
                if (source.charAt(i - 1) == target.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int insert =
                            dp[i][j - 1] + 1; // source[0,i] to target[0,j-1] then insert target[j]
                    int delete =
                            dp[i - 1][j] + 1; // source[0,i-1] to target[0,j] then delete source[i]
                    int substitute =
                            dp[i - 1][j - 1]
                                    + 2; // source[0,i-1] to target[0,j-1] then substitute(source[i]
                    // by target[j])

                    int min = min(insert, delete, substitute);
                    dp[i][j] = min;
                }
            }
        }
        return dp[sourceLen][targetLen];
    }

    private int min(int insert, int delete, int substitute) {
        int tmp = insert < delete ? insert : delete;
        int min = tmp < substitute ? tmp : substitute;
        return min;
    }
}
